/**
 * Note: The returned array must be malloced, assume caller calls free().
 * ---------------
 * 参考资料
 * https://www.cnblogs.com/jplusztx/p/jplusztx.html
 */

#include <stdio.h>
#include <stdlib.h>
// 这里应该使用 .h 的文件的，但是因为 `Code runner`会编译不过去，就用 .c 。
// 因为我们仅有一个入口文件调用，可用使用 .c ，知道就可以了，我是为了学习思路的。
#include "../utils/c/c_tool.c"
// #include "../utils/c/c_tool.h"

// 4ms
int * twoSum(int * nums, int numsSize, int target, int* returnSize){
  int i, j;
  int *returned = calloc(2, sizeof(int));
  if (!returned) {
    *returnSize = 0;
    return NULL;
  }
  for (i = 0; i < numsSize - 1; i++) {
    for (j = i + 1; j < numsSize; j++) {
      if (nums[i] + nums[j] == target) {
        returned[0] = i;
        returned[1] = j;        
        *returnSize = 2;
        return returned;
      }
    }
  }
  *returnSize = 0;
  return NULL;
}

// 8ms
int* twoSum2(int* nums, int numsSize, int target, int* returnSize){ 
  int *returned = calloc(2, sizeof(int));
  if (!returned) {
    *returnSize = 0;
    return NULL;
  }
  
  int p1 = 0;
  int p2 = 1;
  while (1) {
    if (p2 >= numsSize) {
      p1 ++;
      if (p1 > numsSize) {
        break;
      }
      p2 = p1 + 1;
      continue;
    }
    int value1 = *(nums + p1);
    int value2 = *(nums + p2);
    if (value1 + value2 == target) {
      returned[0] = p1;
      returned[1] = p2;
      *returnSize = 2;
      return returned;
    }
    p2++;
  }
  return NULL;
}

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
// 最优写法
int* twoSum3(int* nums, int numsSize, int target, int* returnSize){
  int *p = (int *)malloc(sizeof(int) * 2);
  for (int i = 0;i < numsSize - 1; i++)
    for (int j = i + 1; j < numsSize; j++)
        if (*(nums + i) + *(nums + j) == target) {
          *p = i;
          *(p + 1) = j;
          goto lable;
        }

  lable: {   
    *returnSize = 2;
    return p;
  }      
}

int main() {
  int nums[] = {2, 7, 1, 0, 11, 15};
  int numsSize = sizeof(nums) / sizeof(nums[0]);
  int target = 2;
  int * returnSize = calloc(2, sizeof(int));

  ToolPrintArray(nums, numsSize);
  printf("target=%d", target);
  printf("\n-------\n");

  clock_t start, end;
  /*记录循环开始的时间*/
  start = clock();
  // int * returned = twoSum(nums, numsSize, target, returnSize);
  // int * returned = twoSum2(nums, numsSize, target, returnSize);
  int * returned = twoSum3(nums, numsSize, target, returnSize);
  /*记录循环结束的时间*/
  end = clock();
  ToolPrintRunTime(start, end);

  int length = *returnSize;
  printf("length=%d", length);
  ToolPrintArray(returned, length);
}